{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 分子表面网格生成与优化"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "分子表面网格对许多问题都是很重要的,例如在分子结构分析,对接问题等方面的作用,所以对分子表面提供一个好的网格对解决问题非常重要.分子是由许多个小原子拼接而成.而每个小原子都可以看成是一个小球,设分子就是由这 $N$ 个小球拼接而成,且每个小球的球心为 $c_i$,半径是 $r_i$.则分子表面的水平集函数 $\\phi(x)$ 可以表示为:\n",
    "\n",
    "$$\n",
    "\\phi(\\vec x)=\\sum_{j=1}^{N}e^{-d(| x- c_i|^2/r_i^2-1)}-t_0\n",
    "$$\n",
    "\n",
    "其中,\n",
    "\n",
    "$$\n",
    "d=0.5,t_0=1\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "主要可以从以下几方面做.\n",
    "1. 对水平集函数$\\phi(x)$的快速计算;\n",
    "1. 生成一个初始网格;\n",
    "1. 网格的优化.而困难的地方在于分子数目 $N$ 很大时,如达到上百万的情况,计算是比较复杂,而且耗时比较多.因此需要给定分子的一个点 $x$ ,运用空间搜索法来找出 $x$ 附近的几个原子."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 一 水平集函数 $\\phi(x)$ 的快速计算"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "水平集函数 $\\phi(x)$ 的指数具有快速衰减的性质,所以当点 $x$ 远离原子时,该原子的贡献几乎可以忽略不计.只需要计算 $x$ 附近的几个原子的指数函数即可.那么如何找出 $x$ 附近的原子?可以用以下几种方法来找出 $x$ 附近的原子.\n",
    "\n",
    "1. 用八叉树来找出  $x$ 附近的原子;\n",
    "1. 用 $kd$ 树来找出  $x$ 附近的原子;\n",
    "1. 用四面体网格自适应算法来找出  $x$ 附近的原子;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 八叉树(Octree)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 八叉树(Octree)的定义"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "八叉树是一种用于描述三维空间的树状数据结构.八叉树的每个结点表示一个正方体的体积元素,每个节点有八个子结点,将八个子结点表示的体积元素加在一起就等于父结点的体积.\n",
    "\n",
    "八叉树若不为空树的话,树的任意结点的子结点恰好只会有八个,或者零个,也就是子结点不会有0与8以外的数目.\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 八叉树算法思想"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "八叉树剖分算法是一个空间非均匀网格剖分算法,该算法将含有整个场景的空间立方体按三个方向的中剖分面分割成八个子立方体网格,组成一棵八叉树,若某一立方体网格中所含原子个数大于给定的原子个数时,将该立方体进一步剖分.重复上述过程,直至八叉树每一个叶子结点所含原子个数小于等于给定的原子个数."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 八叉树算法步骤"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    " 八叉树的算法步骤包括:\n",
    "1. 设定最大递归深度(八叉树最大层数);\n",
    "1. 找出场景的最大尺寸,并且以尺寸建立第一个立方体(包围盒);\n",
    "1. 依序将单位元素丢入能被包含且没有子结点的立方体;\n",
    "1. 若没有达到最大递归深度,就进行八等份细分,再将该立方体所装的单位元素全部分担给八个子结点立方体;\n",
    "1. 若发现子立方体所分配到的单位元素数量不为零且跟父立方体是一样的,则该子结点立方体停止细分,因为根据空间分割理论,细分空间所得到的分配必定较少,若是一样数目,则再怎么切数目还是一样,会造成无穷切割的情形;\n",
    "1. 重复步骤三,直到达到最大递归深度."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 寻找 $x$ 附近原子的算法代码"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. $kd$ 树\n",
    "1. 四面体网格自适应算法\n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 二 一致的网格情形"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给出一个立方体 $[0,1]^3$, 取步长为 $h$, 把 $x,y,z$ 每个方向分为 $1 \\over h$ 条边, 则每个方向都有 $N= \\frac{1}{h}+1$ 个点. 现给出一个指标集 $(i,j,k)$ 来找出它所有的边.\n",
    "先生成一个立方体网格,再找出该立方体的每一条边.\n",
    "\n",
    "* 网格生成算法\n",
    "    1. 定义一个函数;\n",
    "    1. 给出三个坐标轴的六个端点;\n",
    "    1. 给出步长为 $h$ ,求出节点的总数;\n",
    "    1. 给每个节点标号;\n",
    "    1. 给出每个节点的坐标;\n",
    "    1. 生成图像;\n",
    "* 网格生成代码"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.5.2"
  },
  "latex_envs": {
   "LaTeX_envs_menu_present": true,
   "bibliofile": "biblio.bib",
   "cite_by": "apalike",
   "current_citInitial": 1,
   "eqLabelWithNumbers": true,
   "eqNumInitial": 0
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
